import java.util.ArrayList;
import java.util.List;

// 力扣211. 添加与搜索单词 - 数据结构设计
class TrieNode {
    TrieNode[] children;
    boolean isWord;

    public TrieNode() {
        children = new TrieNode[26]; // 26个小写字母
        isWord = false;
    }
}
class WordDictionary {
    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        return searchHelper(word, 0, root);
    }

    private boolean searchHelper(String word, int index, TrieNode node) {
        if (index == word.length()) {
            return node.isWord;
        }

        char c = word.charAt(index);
        if (c == '.') {
            for (TrieNode child : node.children) {
                if (child != null && searchHelper(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            int childIndex = c - 'a';
            if (node.children[childIndex] == null) {
                return false;
            }
            return searchHelper(word, index + 1, node.children[childIndex]);
        }
    }
}



// 力扣212. 单词搜索 II
class Solution1 {
    // 定义字典树节点
    class TrieNode {
        TrieNode[] children;
        String word;

        public TrieNode() {
            children = new TrieNode[26];
            word = null;
        }
    }

    // 构建字典树
    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new TrieNode();
                }
                node = node.children[index];
            }
            node.word = word; // 在单词结尾节点存储完整单词
        }
        return root;
    }

    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        TrieNode root = buildTrie(words);

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, result);
            }
        }

        return result;
    }

    private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
        char c = board[i][j];
        // 检查当前字符是否在字典树中
        if (c == '#' || node.children[c - 'a'] == null) {
            return;
        }

        node = node.children[c - 'a'];
        // 如果找到一个单词
        if (node.word != null) {
            result.add(node.word);
            node.word = null; // 避免重复添加
        }

        // 标记已访问
        board[i][j] = '#';
        // 四个方向搜索
        if (i > 0) dfs(board, i - 1, j, node, result); // 上
        if (j > 0) dfs(board, i, j - 1, node, result); // 左
        if (i < board.length - 1) dfs(board, i + 1, j, node, result); // 下
        if (j < board[0].length - 1) dfs(board, i, j + 1, node, result); // 右
        // 恢复
        board[i][j] = c;
    }
}